package advanced.class_append;

import java.util.Arrays;
import java.util.LinkedList;

// 获取窗口内的最大值
public class Code_01_MaxWindow {

    public static int getMaxValue(int[] arr, int l, int r) {
        if(l < 0 || r >= arr.length || l > r) {
            throw new RuntimeException("参数输出有误！");
        }
        // 创建一个双端队列
        LinkedList<Integer> list = new LinkedList<>();
        // 从数组l位置向队列中添加元素
        for (int i = l; i <= r; i++) {
            while(!list.isEmpty() && arr[list.peekLast()] <= arr[i]){
                list.pollLast();  // 从尾部弹出元素
            }
            list.addLast(i);
        }
        return arr[list.peekFirst()];
    }

    public static int[] getMaxWindow(int[] arr, int w) {
        if(arr == null || w < 1 || w > arr.length) return null;
        // 创建双端队列
        LinkedList<Integer> list = new LinkedList<Integer>();
        int[] res = new int[arr.length - w + 1];
        int index = 0;
        for (int i = 0; i < arr.length; i++) {
            while(!list.isEmpty() && arr[list.peekLast()] <= arr[i]){
                list.pollLast();
            }
            list.addLast(i);
            if(list.peekFirst() == i - w){
                list.pollFirst();
            }
            if(i >= w - 1){
                res[index++] = arr[list.peekFirst()];
            }
        }
        return res;
    }

    public static int getNum(int[] arr, int num){
        if(arr == null || arr.length == 0) return 0;
        // 创建两个双端队列
        LinkedList<Integer> dpMin = new LinkedList<Integer>();
        LinkedList<Integer> dpMax = new LinkedList<Integer>();
        // 设置左右指针
        int res = 0;
        int L = 0;
        int R = 0;
        while(L < arr.length){
            while(R < arr.length){
                // 更新两个双端队列
                while(!dpMax.isEmpty() && arr[dpMax.peekLast()] <= arr[R]){
                    dpMax.pollLast();
                }
                dpMax.addLast(R);
                while(!dpMin.isEmpty() && arr[dpMin.peekLast()] >= arr[R]){
                    dpMin.pollLast();
                }
                dpMin.addLast(R);
                if(arr[dpMax.peekFirst()] - arr[dpMin.peekFirst()] > num){
                    break;
                }
                R++;
            }
            // 去除当前L位置的影响，L右移
            if(dpMin.peekFirst() == L){
                dpMin.pollFirst();
            }
            if(dpMax.pollFirst() == L){
                dpMax.pollFirst();
            }
            res += R - L;
            L++;
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = {1,2,5,3,7,8,4};
        System.out.println(Arrays.toString(getMaxWindow(arr,3)));
    }
}
